An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
Identifieur interne : 008844 ( Main/Exploration ); précédent : 008843; suivant : 008845An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon
Auteurs : -D. Boissonnat ; Ghosh [États-Unis] ; Kavitha [États-Unis] ; LazardSource :
- Algorithmica [ 0178-4617 ] ; 2002-10-01.
English descriptors
- KwdEn :
- mix :
Abstract
Abstract: Abstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature(i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points sand tinside Pand two directions of travel, one at sand one at t , the problem is to compute a convex and simple path of bounded curvature inside Pfrom sto tconsisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at sis tangent to the path at sand (iv) the given final direction at tis tangent to the path at t . We propose an O(n4)time algorithm for this problem. Using the notion of complete visibility, Pis pruned to another polygon P'such that any convex and simple path from sto tinside Palso remains inside P' . Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P'and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in O(n)time to a minimalconvex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimalbounded curvature path is located in O(n4)time whose length, except in special situations involving arcs of length greater than π , is at most twice the length of a shortest convex and simple path of bounded curvature.
Url:
DOI: 10.1007/s00453-002-0950-0
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003279
- to stream Istex, to step Curation: 003238
- to stream Istex, to step Checkpoint: 001C80
- to stream Hal, to step Corpus: 000D58
- to stream Hal, to step Curation: 000D58
- to stream Hal, to step Checkpoint: 005A47
- to stream Main, to step Merge: 008D00
- to stream Main, to step Curation: 008844
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon</title>
<author><name sortKey=" D Boissonnat" sort=" D Boissonnat" uniqKey=" D Boissonnat" first="" last="-D. Boissonnat">-D. Boissonnat</name>
</author>
<author><name sortKey="Ghosh" sort="Ghosh" uniqKey="Ghosh" first="" last="Ghosh">Ghosh</name>
</author>
<author><name sortKey="Kavitha" sort="Kavitha" uniqKey="Kavitha" first="" last="Kavitha">Kavitha</name>
</author>
<author><name sortKey="Lazard" sort="Lazard" uniqKey="Lazard" first="" last="Lazard">Lazard</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:D51FE1DA86EE8DE4EDB337C0F209AB450D719D45</idno>
<date when="2002" year="2002">2002</date>
<idno type="doi">10.1007/s00453-002-0950-0</idno>
<idno type="url">https://api.istex.fr/ark:/67375/VQC-946H9R1G-T/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003279</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003279</idno>
<idno type="wicri:Area/Istex/Curation">003238</idno>
<idno type="wicri:Area/Istex/Checkpoint">001C80</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001C80</idno>
<idno type="wicri:doubleKey">0178-4617:2002: D Boissonnat:an:algorithm:for</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00100533</idno>
<idno type="url">https://hal.inria.fr/inria-00100533</idno>
<idno type="wicri:Area/Hal/Corpus">000D58</idno>
<idno type="wicri:Area/Hal/Curation">000D58</idno>
<idno type="wicri:Area/Hal/Checkpoint">005A47</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">005A47</idno>
<idno type="wicri:doubleKey">0178-4617:2002:Boissonnat J:an:algorithm:for</idno>
<idno type="wicri:Area/Main/Merge">008D00</idno>
<idno type="wicri:Area/Main/Curation">008844</idno>
<idno type="wicri:Area/Main/Exploration">008844</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon</title>
<author><name sortKey=" D Boissonnat" sort=" D Boissonnat" uniqKey=" D Boissonnat" first="" last="-D. Boissonnat">-D. Boissonnat</name>
<affiliation><wicri:noCountry code="subField">FR</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Ghosh" sort="Ghosh" uniqKey="Ghosh" first="" last="Ghosh">Ghosh</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<placeName><region type="state">Indiana</region>
</placeName>
<wicri:cityArea>School of Computer Science, Tata Institute of Fundamental Research, Mumbai 400005, India. ghosh@tifr.res.in. kavita@tcs.tifr.res.in.</wicri:cityArea>
</affiliation>
</author>
<author><name sortKey="Kavitha" sort="Kavitha" uniqKey="Kavitha" first="" last="Kavitha">Kavitha</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<placeName><region type="state">Indiana</region>
</placeName>
<wicri:cityArea>School of Computer Science, Tata Institute of Fundamental Research, Mumbai 400005, India. ghosh@tifr.res.in. kavita@tcs.tifr.res.in.</wicri:cityArea>
</affiliation>
</author>
<author><name sortKey="Lazard" sort="Lazard" uniqKey="Lazard" first="" last="Lazard">Lazard</name>
<affiliation><wicri:noCountry code="subField">FR</wicri:noCountry>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Algorithmica</title>
<title level="j" type="abbrev">Algorithmica</title>
<idno type="ISSN">0178-4617</idno>
<idno type="eISSN">1432-0541</idno>
<imprint><publisher>Springer-Verlag</publisher>
<pubPlace>Berlin/Heidelberg</pubPlace>
<date type="published" when="2002-10-01">2002-10-01</date>
<biblScope unit="volume">34</biblScope>
<biblScope unit="issue">2</biblScope>
<biblScope unit="page" from="109">109</biblScope>
<biblScope unit="page" to="156">156</biblScope>
</imprint>
<idno type="ISSN">0178-4617</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0178-4617</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Key words. Non-holonomic, Motion planning, Curvature constrained path, Euclidean shortest path, Link path, Visibility, Approximation algorithm.</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>chemins de courbure bornée</term>
<term>non-holonomic motion planning</term>
<term>paths of bonded curvature</term>
<term>planification de trajectoire non-holonome</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Abstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature(i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points sand tinside Pand two directions of travel, one at sand one at t , the problem is to compute a convex and simple path of bounded curvature inside Pfrom sto tconsisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at sis tangent to the path at sand (iv) the given final direction at tis tangent to the path at t . We propose an O(n4)time algorithm for this problem. Using the notion of complete visibility, Pis pruned to another polygon P'such that any convex and simple path from sto tinside Palso remains inside P' . Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P'and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in O(n)time to a minimalconvex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimalbounded curvature path is located in O(n4)time whose length, except in special situations involving arcs of length greater than π , is at most twice the length of a shortest convex and simple path of bounded curvature.</div>
</front>
</TEI>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Indiana</li>
</region>
</list>
<tree><noCountry><name sortKey=" D Boissonnat" sort=" D Boissonnat" uniqKey=" D Boissonnat" first="" last="-D. Boissonnat">-D. Boissonnat</name>
<name sortKey="Lazard" sort="Lazard" uniqKey="Lazard" first="" last="Lazard">Lazard</name>
</noCountry>
<country name="États-Unis"><region name="Indiana"><name sortKey="Ghosh" sort="Ghosh" uniqKey="Ghosh" first="" last="Ghosh">Ghosh</name>
</region>
<name sortKey="Kavitha" sort="Kavitha" uniqKey="Kavitha" first="" last="Kavitha">Kavitha</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 008844 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 008844 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:D51FE1DA86EE8DE4EDB337C0F209AB450D719D45 |texte= An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon }}
This area was generated with Dilib version V0.6.33. |